/*   The MIT License
 *   
 *   Carina Common
 *   Copyright (c) 2010-2011 Zdravko Velinov
 *   
 *   Permission is hereby granted, free of charge, to any person obtaining a copy
 *   of this software and associated documentation files (the "Software"), to deal
 *   in the Software without restriction, including without limitation the rights
 *   to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *   copies of the Software, and to permit persons to whom the Software is
 *   furnished to do so, subject to the following conditions:
 *
 *   The above copyright notice and this permission notice shall be included in
 *   all copies or substantial portions of the Software.
 *
 *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *   THE SOFTWARE.
 */

#ifndef CONTAINERS_H_
#define CONTAINERS_H_

#include "carina/common/global.hh"
#include "carina/common/memory.hh"
#include "carina/common/assert.hh"

#include <cassert>
#include <cstddef>

namespace Carina
{
template<class T, int alignment = alignment_of<T>::value> class DAAllocator;

template<class T, int alignment>
class DAAllocator
{
public:
    T* allocate(size_t n) const
    {
        return static_cast<T*>(::operator new(sizeof(T)*n));
    }
    void deallocate(T* ptr) const
    {
        ::operator delete(ptr);
    }
};

template<class T>
class DAAllocator<T, 16>
{
public:
    T* allocate(size_t n) const
    {
        void* ptr;
        __ALIGNED_ALLOC(ptr, n*sizeof(T), 16);
        return reinterpret_cast<T*>(ptr);
    }

    void deallocate(T* ptr) const
    {
        __ALIGNED_DEALLOC(ptr);
    }
};

/*! \brief Forward iterator object used by Array.
 *  \tparam T   the data type over which the object is iterating.
 */
template<class T>
class ArrayIterator
{
    T* m_Ptr;   //! Pointer to current element.
public:
    //! Iterator type declaration.
    typedef std::random_access_iterator_tag iterator_category;
    //! The data type of each element.
    typedef T                               value_type;
    //! The data type used for returning the difference between two iterators.
    typedef int                             difference_type;
    //! The data type used for returning a pointer to the current element.
    typedef T*                              pointer;
    //! The data type used for returning a reference to the current element.
    typedef T&                              reference;

    //! Default constructor.
    explicit ArrayIterator()
		:   m_Ptr(nullptr) {}

    //! Constructor (for internal usage by container classes).
    explicit ArrayIterator(T* ptr)
        :   m_Ptr(ptr) {}

    //! Copy constructor.
    ArrayIterator(const ArrayIterator& iter)
        :   m_Ptr(iter.m_Ptr) {}

    //! Assignment operator.
    ArrayIterator& operator=(const ArrayIterator& iter) { m_Ptr = iter.m_Ptr; return *this; }

    //! Difference operator.
    difference_type operator-(const ArrayIterator& iter) const { return m_Ptr - iter.m_Ptr; }

    //! Step increment operator.
    ArrayIterator operator+(size_t i) const { return ArrayIterator(m_Ptr + i); }

    //! Step decrement operator.
    ArrayIterator operator-(size_t i) const { return ArrayIterator(m_Ptr - i); }

    //! Prefix decrement operator.
    ArrayIterator& operator--() { --m_Ptr; return *this; }

    //! Prefix increment operator.
    ArrayIterator& operator++() { ++m_Ptr; return *this; }

    //! Postfix decrement operator.
    ArrayIterator operator--(int) { ArrayIterator tmp(*this); ++m_Ptr; return tmp; }

    //! Postfix increment operator.
    ArrayIterator operator++(int) { ArrayIterator tmp(*this); --m_Ptr; return tmp; }

    //! Equal-to operator.
    bool operator==(const ArrayIterator& iter) const { return m_Ptr == iter.m_Ptr; }

    //! Not-equal-to operator.
    bool operator!=(const ArrayIterator& iter) const { return m_Ptr != iter.m_Ptr; }

    //! Greater-than operator.
    bool operator>(const ArrayIterator& iter) const { return m_Ptr > iter.m_Ptr; }

    //! Lesser-than operator.
    bool operator<(const ArrayIterator& iter) const { return m_Ptr < iter.m_Ptr; }

    //! Lesser-than-or-equal-to operator.
    bool operator<=(const ArrayIterator& iter) const { return m_Ptr <= iter.m_Ptr; }

    //! Greater-than-or-equal-to operator.
    bool operator>=(const ArrayIterator& iter) const { return m_Ptr >= iter.m_Ptr; }

    //! Addition-assignment operator.
    ArrayIterator& operator+=(size_t i) { m_Ptr += i; return *this; }

    //! Subtraction-assignment operator.
    ArrayIterator& operator-=(size_t i) { m_Ptr -= i; return *this; }
    
    //! Array subscript operator.
    reference operator[](size_t i) const { m_Ptr[i]; return *this; }

    //! Indirection operator.
    reference operator*() const { return *m_Ptr; }

    //! Structure dereference operator.
    pointer operator->() const { return m_Ptr; }

    //! Casting operator.
    operator ArrayIterator<const T>() const { return ArrayIterator<const T>(m_Ptr); }
};

/*! \brief Reverse iterator object used by Array.
 *  \tparam T   the data type over which the object is iterating.
 */
template<class T>
class ReverseArrayIterator
{
    T* m_Ptr;   //! Pointer to current element.
public:
    //! Iterator type declaration.
    typedef std::random_access_iterator_tag iterator_category;
    //! The data type of each element.
    typedef T                               value_type;
    //! The data type used for returning the difference between two iterators.
    typedef int                             difference_type;
    //! The data type used for returning a pointer to the current element.
    typedef T*                              pointer;
    //! The data type used for returning a reference to the current element.
    typedef T&                              reference;

    //! Default constructor.
    explicit ReverseArrayIterator()
        :   m_Ptr(nullptr) {}

    //! Constructor (for internal usage by container classes).
    explicit ReverseArrayIterator(T* ptr)
        :   m_Ptr(ptr) {}

    //! Copy constructor.
    ReverseArrayIterator(const ReverseArrayIterator<T>& iter)
        :   m_Ptr(iter.m_Ptr) {}

    //! Assignment operator.
    ReverseArrayIterator& operator=(const ReverseArrayIterator& iter) { m_Ptr = iter.m_Ptr; return *this; }

    //! Difference operator.
    difference_type operator-(const ReverseArrayIterator& iter) const { return m_Ptr - iter.m_Ptr; }

    //! Step increment operator.
    ReverseArrayIterator operator+(size_t i) const { return ReverseArrayIterator(m_Ptr - i); }

    //! Step decrement operator.
    ReverseArrayIterator operator-(size_t i) const { return ReverseArrayIterator(m_Ptr + i); }

    //! Prefix decrement operator.
    ReverseArrayIterator& operator--() { ++m_Ptr; return *this; }

    //! Prefix increment operator.
    ReverseArrayIterator& operator++() { --m_Ptr; return *this; }

    //! Postfix decrement operator.
    ReverseArrayIterator operator--(int) { ReverseArrayIterator tmp(*this); ++m_Ptr; return tmp; }

    //! Postfix increment operator.
    ReverseArrayIterator operator++(int) { ReverseArrayIterator tmp(*this); --m_Ptr; return tmp; }

    //! Equal-to operator.
    bool operator==(const ReverseArrayIterator& iter) const { return m_Ptr == iter.m_Ptr; }

    //! Not-equal-to operator.
    bool operator!=(const ReverseArrayIterator& iter) const { return m_Ptr != iter.m_Ptr; }

    //! Greater-than operator.
    bool operator>(const ReverseArrayIterator& iter) const { return m_Ptr < iter.m_Ptr; }

    //! Lesser-than operator.
    bool operator<(const ReverseArrayIterator& iter) const { return m_Ptr > iter.m_Ptr; }

    //! Lesser-than-or-equal-to operator.
    bool operator<=(const ReverseArrayIterator& iter) const { return m_Ptr >= iter.m_Ptr; }

    //! Greater-than-or-equal-to operator.
    bool operator>=(const ReverseArrayIterator& iter) const { return m_Ptr <= iter.m_Ptr; }

    //! Addition-assignment operator.
    ReverseArrayIterator& operator+=(size_t i) { m_Ptr -= i; return *this; }

    //! Subtraction-assignment operator.
    ReverseArrayIterator& operator-=(size_t i) { m_Ptr += i; return *this; }
    
    //! Array subscript operator.
    reference operator[](size_t i) const { m_Ptr[-i]; return *this; }

    //! Indirection operator.
    reference operator*() const { return *m_Ptr; }

    //! Structure dereference operator.
    pointer operator->() const { return m_Ptr; }

    //! Casting operator.
    operator ReverseArrayIterator<const T>() const { return ReverseArrayIterator<const T>(m_Ptr); }
};

/* TODO: optimized version for fundamental data types */
const size_t dv_capacity_step = 8;

template<class T, class TAlloc = DAAllocator<T> >
class DataVector
{
    TAlloc  m_Alloc;
    size_t  m_Size;
    size_t  m_Capacity;
    T*      m_Data;
public:
    typedef T                               value_type;
    typedef ArrayIterator<T>                iterator;
    typedef ArrayIterator<const T>          const_iterator;
    typedef ReverseArrayIterator<T>         reverse_iterator;
    typedef ReverseArrayIterator<const T>   const_reverse_iterator;

    DataVector()
        :   m_Size(0),
            m_Capacity(dv_capacity_step),
            m_Data(m_Alloc.allocate(dv_capacity_step)) {}

    ~DataVector()
    {
        while(m_Size)
            m_Data[--m_Size].~T();
        m_Alloc.deallocate(m_Data);
    }

    DataVector(size_t s, const T& t = T())
        :   m_Size(0)
    {
        m_Capacity = s + dv_capacity_step;
        m_Data = m_Alloc.allocate(m_Capacity);
        while(m_Size < s)
            new (&m_Data[m_Size++]) T(t);
    }

    DataVector(const T* t, size_t n)
    {
        m_Size = n;
        m_Capacity = n + dv_capacity_step;
        m_Data = m_Alloc.allocate(m_Capacity);
        for(size_t i = 0; i < m_Size; ++i)
            new (&m_Data[i]) T(t[i]);
    }

    DataVector(const DataVector& arr)
    {
        m_Size = arr.m_Size;
        m_Capacity = arr.m_Capacity;
        m_Data = m_Alloc.allocate(m_Capacity);
        for(size_t i = 0; i < m_Size; ++i)
            new (&m_Data[i]) T(arr.m_Data[i]);
    }

    DataVector& operator=(const DataVector& arr)
    {
        clear();
        m_Size = arr.m_Size;
        m_Capacity = arr.m_Capacity;
        m_Data = m_Alloc.allocate(m_Capacity);
        for(size_t i = 0; i < m_Size; ++i)
            new (&m_Data[i]) T(arr.m_Data[i]);
        return *this;
    }

    template<class InputIterator>
    void assign(InputIterator first, InputIterator last)
    {
        InputIterator i;
        size_t j;
        clear();
        m_Size = std::distance(first, last);
        m_Capacity = m_Size + dv_capacity_step;
        m_Data = m_Alloc.allocate(m_Capacity);
        for(i = first, j = 0; i != last; ++i, ++j)
            new (&m_Data[j]) T(*i);
    }

    void assign(const T* data, size_t size)
    {
        clear();
        m_Size = size;
        m_Capacity = m_Size + dv_capacity_step;
        m_Data = m_Alloc.allocate(m_Capacity);
        for(size_t i = 0; i < m_Size; ++i)
            new (&m_Data[i]) T(data[i]);
    }

    iterator begin() { return iterator(m_Data); }
    const_iterator begin() const { return const_iterator(m_Data); }

    iterator end() { return iterator(m_Data+m_Size); }
    const_iterator end() const { return const_iterator(m_Data+m_Size); }

    T& front() { CE_ASSERT(m_Size > 0, "Accessing the first element of empty array"); return *m_Data; }
    const T& front() const { CE_ASSERT(m_Size > 0, "Accessing the first element of empty array"); return *m_Data; }

    T& back() { CE_ASSERT(m_Size > 0, "Accessing the last element of empty array"); return m_Data[m_Size - 1]; }
    const T& back() const { CE_ASSERT(m_Size > 0, "Accessing the last element of empty array"); return m_Data[m_Size - 1]; }

    T& operator[](size_t i) { CE_ASSERT(i < m_Size, "Accessing element beyond the array's upper boundary. Possible buffer overflow."); return m_Data[i]; }
    const T& operator[](size_t i) const { CE_ASSERT(i < m_Size, "Accessing element beyond the array's upper boundary. Possible buffer overflow."); return m_Data[i]; }

    T& at(size_t i) { CE_ASSERT(i < m_Size, "Accessing element beyond the array's upper boundary. Possible buffer overflow."); return m_Data[i]; }
    const T& at(size_t i) const { CE_ASSERT(i < m_Size, "Accessing element beyond the array boundary. Possible buffer overflow."); return m_Data[i];  }

    size_t size() const { return m_Size; }

    T* get() { return m_Data; }
    const T* get() const { return m_Data; }

    void resize(size_t n, const T& t = T())
    {
        if(m_Size < n)
        {
            if(m_Capacity < n )
            {
                m_Capacity = n + dv_capacity_step;
                T* newData = m_Alloc.allocate(m_Capacity);
                for(size_t i = 0; i < m_Size; ++i)
                    new (&newData[i]) T(m_Data[i]);
                for(size_t i = m_Size; i < n; ++i)
                    new (&newData[i]) T(t);
                for(size_t i = 0; i < m_Size; ++i)
                    m_Data[i].~T();
                m_Alloc.deallocate(m_Data);
                m_Data = newData;
            }
            else
                for(size_t i = m_Size; i < n; ++i)
                    new(&m_Data[i]) T(t);
        }
        else
            for(size_t i = n; i < m_Size; ++i)
                m_Data[i].~T();

        m_Size = n;
    }

    void insert(size_t idx, const T& t)
    {
        CE_ASSERT(idx <= m_Size, "Insertion beyond the array upper boundary and its current end.");
        if(m_Size+1 > m_Capacity)
        {
            m_Capacity += dv_capacity_step;
            T* newData = m_Alloc.allocate(m_Capacity);
            for(size_t i = 0; i < idx; ++i)
                new (&newData[i]) T(m_Data[i]);
            new (&newData[idx]) T(t);
            for(size_t i = idx; i < m_Size; ++i)
                new (&newData[i+1]) T(m_Data[i]);
            for(size_t i = 0; i < m_Size; ++i)
                m_Data[i].~T();
            m_Alloc.deallocate(m_Data);
            m_Data = newData;
        }
        else
        {
            for(size_t i = m_Size; i > idx; --i)
            {
                new(&m_Data[i]) T(m_Data[i-1]);
                m_Data[i-1].~T();
            }
            new (&m_Data[idx]) T(t);
        }
        ++m_Size;
    }

    template<class Iterator>
    void insert(Iterator iter, const T& t)
    {
        int idx = std::distance(begin(), iter);
        CE_ASSERT(idx >= 0, "Insertion under the array's lower boundary.");
        insert((size_t)idx, t);
    }

    void insert(size_t idx, size_t num, const T& t)
    {
        CE_ASSERT(idx <= m_Size, "Insertion beyond the array's upper boundary.");
        if(m_Size+num > m_Capacity)
        {
            m_Capacity += dv_capacity_step + num;
            T* newData = m_Alloc.allocate(m_Capacity);
            for(size_t i = 0; i < idx; ++i)
                new (&newData[i]) T(m_Data[i]);
            for(size_t i = 0; i < num; ++i)
                new (&newData[idx+i]) T(t);
            for(size_t i = idx; i < m_Size; ++i)
                new (&newData[i+num]) T(m_Data[i]);
            for(size_t i = 0; i < m_Size; ++i)
                m_Data[i].~T();
            m_Alloc.deallocate(m_Data);
            m_Data = newData;
        }
        else
        {
            for(size_t i = m_Size; i > idx; --i)
            {
                new (&m_Data[i+num-1]) T(m_Data[i-1]);
                m_Data[i-1].~T();
            }
            for(size_t i = 0; i < num; ++i)
                new (&m_Data[idx+i]) T(t);
        }
        m_Size += num;
    }

    template<class Iterator>
    void insert(Iterator iter, size_t num, const T& t)
    {
        int idx = std::distance(begin(), iter);
        CE_ASSERT(idx >= 0, "Insertion under the array's lower boundary.");
        insert((size_t)idx, num, t);
    }

    template<typename InputIterator>
    void insert(iterator pos, InputIterator first, InputIterator last)
    {
        InputIterator itr;
        size_t  i,
                idx = std::distance(begin(), pos),
                num = std::distance(first, last);
        assert(idx <= m_Size);
        if(m_Size+num > m_Capacity)
        {
            m_Capacity += dv_capacity_step + num;
            T* newData = m_Alloc.allocate(m_Capacity);
            for(i = 0; i < idx; ++i)
                new (&newData[i]) T(m_Data[i]);
            for(itr = first, i = idx; itr != last; ++itr, ++i)
                new (&newData[i]) T(*itr);
            for(i = idx; i < m_Size; ++i)
                new (&newData[i+num]) T(m_Data[i]);
            for(i = 0; i < m_Size; ++i)
                m_Data[i].~T();
            m_Alloc.deallocate(m_Data);
            m_Data = newData;
        }
        else
        {
            for(i = m_Size; i > idx; --i)
            {
                new (&m_Data[i+num-1]) T(m_Data[i-1]);
                m_Data[i-1].~T();
            }
            for(itr = first, i = idx; itr != last; ++itr, ++i)
                new (&m_Data[i]) T(*itr);
        }
        m_Size += num;
    }

    void pop_back()
    {
        m_Data[--m_Size].~T();
    }

    void push_back(const T& t)
    {
        if(m_Size == m_Capacity)
        {
            m_Capacity += dv_capacity_step;
            T* newData = m_Alloc.allocate(m_Capacity);
            for(size_t i = 0; i < m_Size; ++i)
                new (&newData[i]) T(m_Data[i]);
            new (&newData[m_Size]) T(t);
            for(size_t i = 0; i < m_Size; ++i)
                m_Data[i].~T();
            m_Alloc.deallocate(m_Data);
            m_Data = newData;
        }
        else
            new (&m_Data[m_Size]) T(t);
        ++m_Size;
    }

    void clear()
    {
        while(m_Size)
            m_Data[--m_Size].~T();
    }

    void erase(iterator iter)
    {
        erase(std::distance(begin(), iter));
    }

    void erase(size_t idx)
    {
        assert(idx < m_Size);
        m_Data[idx].~T();
        for(size_t i = idx+1; i < m_Size; ++i)
        {
            new (&m_Data[i-1]) T(m_Data[i]);
            m_Data[i].~T();
        }
        --m_Size;
    }

    void erase(size_t lhs, size_t rhs)
    {
        assert(lhs <= rhs && rhs <= m_Size);
        size_t i, count = rhs-lhs;
        for(i = lhs; i < rhs; ++i)
            m_Data[i].~T();
        for(; i < m_Size; ++i)
        {
            new (&m_Data[i-count]) T(m_Data[i]);
            m_Data[i].~T();
        }
        m_Size -= count;
    }
    
    void reserve(size_t count)
    {
        if(m_Capacity > count)
            return;
        T* newData = m_Alloc.allocate(count);
        for(size_t i = 0; i < m_Size; ++i)
            newData[i] = m_Data[i];
        for(size_t i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
    }

    bool empty() const { return !m_Size; }

    void swap(DataVector& arr)
    {
        std::swap(m_Data, arr.m_Data);
        std::swap(m_Size, arr.m_Size);
        std::swap(m_Capacity, arr.m_Capacity);
    }
};

template< class T, class TAlloc = DAAllocator<T> >
class DynamicArray
{
    TAlloc  m_Alloc;
    size_t  m_Size;
    T*      m_Data;
public:
    typedef T                               value_type;
    typedef ArrayIterator<T>                iterator;
    typedef ArrayIterator<const T>          const_iterator;
    typedef ReverseArrayIterator<T>         reverse_iterator;
    typedef ReverseArrayIterator<const T>   const_reverse_iterator;

    DynamicArray(size_t s, const T& t = T())
        :   m_Size(0)
    {
        m_Data = m_Alloc.allocate(s);
        while(m_Size < s)
            new (&m_Data[m_Size++]) T(t);
    }

    DynamicArray()
        :   m_Size(0),
            m_Data(nullptr) {}

    ~DynamicArray()
    {
        while(m_Size)
            m_Data[--m_Size].~T();
        m_Alloc.deallocate(m_Data);
    }

    DynamicArray(const T* t, size_t n)
    {
        m_Size = n;
        m_Data = m_Alloc.allocate(n);
        for(size_t i = 0; i < m_Size; ++i)
            new (&m_Data[i]) T(t[i]);
    }

    DynamicArray(const DynamicArray& arr)
    {
        m_Size = arr.m_Size;
        m_Data = m_Alloc.allocate(m_Size);
        for(size_t i = 0; i < m_Size; ++i)
            new (&m_Data[i]) T(arr.m_Data[i]);
    }

    DynamicArray& operator=(const DynamicArray& arr)
    {
        clear();
        m_Size = arr.m_Size;
        m_Data = m_Alloc.allocate(m_Size);
        for(size_t i = 0; i < m_Size; ++i)
            new (&m_Data[i]) T(arr.m_Data[i]);
        return *this;
    }

    template<class InputIterator>
    void assign(InputIterator first, InputIterator last)
    {
        InputIterator i;
        size_t j;
        clear();
        m_Size = std::distance(first, last);
        m_Data = m_Alloc.allocate(m_Size);
        for(i = first, j = 0; i != last; ++i, ++j)
            new (&m_Data[j]) T(*i);
    }

    void assign(const T* data, size_t size)
    {
        clear();
        m_Size = size;
        m_Data = m_Alloc.allocate(m_Size);
        for(size_t i = 0; i < m_Size; ++i)
            new (&m_Data[i]) T(data[i]);
    }

    iterator begin() { return iterator(m_Data); }
    const_iterator begin() const { return iterator(m_Data); }

    iterator end() { return iterator(m_Data+m_Size); }
    const_iterator end() const { return iterator(m_Data+m_Size); }

    T& front() { assert(m_Size > 0); return *m_Data; }
    const T& front() const { assert(m_Size > 0); return *m_Data; }

    T& back() { assert(m_Size > 0); return m_Data[m_Size - 1]; }
    const T& back() const { assert(m_Size > 0); return m_Data[m_Size - 1]; }

    T& operator[](size_t i) { assert(i < m_Size); return m_Data[i]; }
    const T& operator[](size_t i) const { assert(i < m_Size); return m_Data[i]; }

    T& at(size_t i) { assert(i < m_Size); return m_Data[i]; }
    const T& at(size_t i) const { assert(i < m_Size); return m_Data[i];  }

    size_t size() const { return m_Size; }

    T* get() { return m_Data; }
    const T* get() const { return m_Data; }

    void resize(size_t n, const T& t = T())
    {
        T* newData = m_Alloc.allocate(n);
        if(m_Size < n)
        {
            for(size_t i = 0; i < m_Size; ++i)
                new (&newData[i]) T(m_Data[i]);
            for(size_t i = m_Size; i < n; ++i)
                new (&newData[i]) T(t);
        }
        else
        {
            for(size_t i = 0; i < n; ++i)
                new (&newData[i]) T(m_Data[i]);
        }
        for(size_t i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
        m_Size = n;
    }

    void insert(size_t idx, const T& t)
    {
        assert(idx <= m_Size);
        T* newData = m_Alloc.allocate(m_Size+1);
        for(size_t i = 0; i < idx; ++i)
            new (&newData[i]) T(m_Data[i]);
        new (&newData[idx]) T(t);
        for(size_t i = idx; i < m_Size; ++i)
            new (&newData[i+1]) T(m_Data[i]);
        for(size_t i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
        ++m_Size;
    }

    template<class Iterator>
    void insert(Iterator iter, const T& t)
    {
        int idx = std::distance(begin(), iter);
        assert(idx >= 0);
        insert((size_t)idx, t);
    }

    void insert(size_t idx, size_t num, const T& t)
    {
        assert(idx <= m_Size);
        T* newData = m_Alloc.allocate(m_Size+num);
        for(size_t i = 0; i < idx; ++i)
            new (&newData[i]) T(m_Data[i]);
        for(size_t i = 0; i < num; ++i)
            new (&newData[idx+i]) T(t);
        for(size_t i = idx; i < m_Size; ++i)
            new (&newData[i+num]) T(m_Data[i]);
        for(size_t i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
        m_Size += num;
    }

    template<class Iterator>
    void insert(Iterator iter, size_t num, const T& t)
    {
        int idx = std::distance(begin(), iter);
        assert(idx >= 0);
        insert((size_t)idx, num, t);
    }
    
    template<typename InputIterator>
    void insert(iterator pos, InputIterator first, InputIterator last)
    {
        InputIterator itr;
        size_t  i,
                idx = std::distance(begin(), pos),
                num = std::distance(first, last);
        assert(num <= m_Size);
        T* newData = m_Alloc.allocate(m_Size + num);
        for(i = 0; i < idx; ++i)
            new (&newData[i]) T(m_Data[i]);
        for(itr = first, i = idx; itr != last; ++itr, ++i)
            new (&newData[i]) T(*itr);
        for(i = idx; i < m_Size; ++i)
            new (&newData[i+num]) T(m_Data[i]);
        for(i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
        m_Size += num;
    }

    void pop_back()
    {
        T* newData = m_Alloc.allocate(--m_Size);
        for(size_t i = 0; i < m_Size; ++i)
            new (&newData[i]) T(m_Data[i]);
        for(size_t i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
    }

    void push_back(const T& t)
    {
        T* newData = m_Alloc.allocate(m_Size+1);
        for(size_t i = 0; i < m_Size; ++i)
            new (&newData[i]) T(m_Data[i]);
        new (&newData[m_Size]) T(t);
        for(size_t i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
        ++m_Size;
    }

    void clear()
    {
        while(m_Size)
            m_Data[--m_Size].~T();
        m_Alloc.deallocate(m_Data);
		m_Data = nullptr;
    }

    void erase(size_t idx)
    {
        assert(idx < m_Size);
        T* newData = m_Alloc.allocate(m_Size-1);
        for(size_t i = 0; i < idx; ++i)
            new (&newData[i]) T(m_Data[i]);
        for(size_t i = idx+1; i < m_Size; ++i)
            new (&newData[i-1]) T(m_Data[i]);
        for(size_t i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
        --m_Size;
    }

    void erase(size_t lhs, size_t rhs)
    {
        assert(lhs <= rhs && rhs <= m_Size);
        size_t count = rhs - lhs;
        T* newData = m_Alloc.allocate(m_Size - count);
        for(size_t i = 0; i < lhs; ++i)
            new (&newData[i]) T(m_Data[i]);
        for(size_t i = rhs; i < m_Size; ++i)
            new (&newData[i-count]) T(m_Data[i]);
        for(size_t i = 0; i < m_Size; ++i)
            m_Data[i].~T();
        m_Alloc.deallocate(m_Data);
        m_Data = newData;
        m_Size -= count;
    }

    bool empty() const { return !m_Size; }

    void swap(DynamicArray& arr)
    {
        std::swap(m_Data, arr.m_Data);
        std::swap(m_Size, arr.m_Size);
    }
};
}

#endif /* CONTAINERS_H_ */
